﻿using System;
using Algoritmia.Problems.Sorting;
using Algoritmia.Utils;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.FractionalKnapsack
{
    public class GreedyFractionalKnapsackSolver : IFractionalKnapsackSolver
    {
        private readonly IInPlaceSorter<Tuple<int,double>> _sorter;

        public GreedyFractionalKnapsackSolver(Func<IInPlaceSorter<Tuple<int,double>>> createSorter = null)
        {
            createSorter = createSorter ?? (() => new SemiIterativeInPlaceQuickSorter<Tuple<int, double>>());
            _sorter = createSorter();
        }

        #region Implementation of IFractionalKnapsackSolver

        public IEnumerable<double> Solve(double W, IEnumerable<double> w, IEnumerable<double> v)
        {
            var values = v.ToList();
            var originalWeightsList = w.ToList();
            var weightsList = originalWeightsList.Select((e,i) => new Tuple<int,double>(i,values[i]/e)).ToAlgoritmiaList();
            _sorter.Sort(weightsList,(tp1,tp2) => tp2.Item2.CompareTo(tp1.Item2) );
            var result = new double[weightsList.Count];
            foreach(var tple in weightsList)
            {
                var i = tple.Item1;
                result[i] = Math.Min(1.0, W / originalWeightsList[i]);
                W -= result[i]*originalWeightsList[i];
            }
            return result;
        }

        #endregion
    }
}
